The paper will study the upper questions based on the two interconnection networks . first , we give a fault - tolerant routing algorithm under the connectivity of the crossed cube in o ( n ) time and the length of the longest routing path ; second , with the rapid progress in vlsi , the failing probability of processors and links is very low , the traditional connectivity underestimates the resilience of large networks / here by applying the concept " conditional connectivity " introduce by harary , we show that the n - crossed cube can tolerate up to 2n - 3 ( n > 2 ) processors failure and remain connected provide that all the neighbors of each processor do not ' fail at the same time , the result is the same as the hypercube . we also give a related algorithm in o ( n ) time , and the length of the longest path ; third , we apply cluster faun tolerance introduced by q . - p 根據(jù)menger定理, n -維交叉立方體可以容納n - 1個故障頂點,我們給出了它的時間復(fù)雜度為o ( n )的容錯路由選擇算法及其最長路徑長度分析;在此基礎(chǔ)上本文證明, n -維交叉立方體的條件連通度為2n - 2 ( n 2 ) ,并給出了相應(yīng)時間復(fù)雜度為o ( n )的算法及其最長路徑長度;除此之外,本文還證明當(dāng)n -維交叉立方體中的故障簇個數(shù)不大于n - 1 ,其直徑不大于1 ,故障頂點總數(shù)不超過2n - 3 ( n 2 )時,交叉立方體中任兩個無故障頂點都至少有一條可靠路徑。
Therefore , it turned out most important that how to find a new kind fault - tolerance model to hold more faulty nodes and how to design more efficient fault - tolerant routing algorithm to ensure accurate and reliable message passing among non - faulty nodes . hypercube is one of the common interconnection networks 因此,如何找出一種新的網(wǎng)絡(luò)容錯模型以便容納更多的錯誤節(jié)點,以及如何設(shè)計高效的容錯路由算法以便保證無故障處理器間正確可靠的信息傳遞是至關(guān)重要的。